Most linear experimental design problems assume homogeneous variance, while the presence of heteroskedastic noise is present in many realistic settings. Let a learner have access to a finite set of measurement vectors that can be probed to receive noisy linear responses. We propose, analyze and empirically evaluate a novel design for uniformly bounding estimation error of the variance parameters. We demonstrate this method on two adaptive experimental design problems under heteroskedastic noise, fixed confidence transductive best-arm identification and level-set identification and prove the first instance-dependent lower bounds in these settings. Lastly, we construct near-optimal algorithms and demonstrate the large improvements in sample complexity gained from accounting for heteroskedastic variance in these designs empirically.
more »
« less
Free, publicly-accessible full text available October 21, 2024
Full Text Available